import entity.TreeNode;

import java.util.LinkedList;

public class SymmetricTree {
    /*
    * 101. 对称二叉树
    * 给你一个二叉树的根节点 root ，检查它是否轴对称。
    *
    * 树中节点数目在范围 [1, 1000] 内
    * -100 <= Node.val <= 100
    *
    * */
    public static void main(String[] args){

    }

    // 我的想法：层次遍历，每层前一半装进栈里，后一半用栈来检测
    // 时空开销都很大，真的很蠢
    public boolean mySolution(TreeNode root){
        LinkedList<TreeNode> deque = new LinkedList<>();
        deque.add(root.left);
        deque.add(root.right);
        while (!deque.isEmpty()){
            LinkedList<TreeNode> stack = new LinkedList<>();
            int size = deque.size() / 2;
            for (int i = 0; i < size; i++) {
                TreeNode cur = deque.pop();
                stack.add(cur); // 入栈等着对比
                if(cur != null){
                    deque.add(cur.left);
                    deque.add(cur.right);
                }
            }
            for (int i = 0; i < size; i++) {
                TreeNode cur = deque.pop();
                TreeNode check = stack.pollLast();
                if(cur == check)
                    continue;
                if(cur != null && check != null){
                    if(cur.val != check.val)
                        return false;
                    deque.add(cur.left);
                    deque.add(cur.right);
                } else {
                    return false;
                }
            }
        }
        return true;
    }

    // 递归
    public boolean solution1(TreeNode root){
        return compare(root.left, root.right);
    }
    // 1. 返回值当然是boolean, 传入值当然是你要比较的左右树
    // 2. 结束条件： 发现不对称，具体如下
    // 3. 迭代处理： 处理匹配对称，递归
    private boolean compare(TreeNode left, TreeNode right){
        if(left == null && right != null) return false;
        if(left != null && right == null) return false;
        if(left == null && right == null) return true;
        if(left.val != right.val) return false;

        // left 和 right相等
        boolean outSide = compare(left.left, right.right);
        boolean inSide = compare(left.right, right.left);
        return outSide && inSide;
    }

    // 迭代 开销比递归大
    public boolean solution2(TreeNode root){
        LinkedList<TreeNode> deque = new LinkedList<>();
        deque.add(root.left);
        deque.add(root.right);
        while (!deque.isEmpty()){
            TreeNode left = deque.pop();
            TreeNode right = deque.pop();
            if(left == right)   // 都为null
                continue;
            if(left == null || right == null || left.val != right.val)
                return false;
            // 相等，按照一定顺序将子节点入队列
            deque.add(left.left);
            deque.add(right.right);
            deque.add(left.right);
            deque.add(right.left);
        }
        return true;
    }
}
